<!DOCTYPE html>
<html lang="en">

<!-- Head tag -->
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="description" content="李修倩在 Github 上的个人博客">
    <meta name="keyword" content="null">
    <meta name="theme-color" content="#600090">
    <meta name="msapplication-navbutton-color" content="#600090">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="#600090">
    <link rel="shortcut icon" href="https://cdn4.iconfinder.com/data/icons/ionicons/512/icon-person-128.png">
    <link rel="alternate" type="application/atom+xml" title="Xiuqianli&#39;s blog" href="/atom.xml">
    <link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/animate.css/3.5.2/animate.min.css">
    <link rel="stylesheet" href="//cdn.bootcss.com/font-awesome/4.6.3/css/font-awesome.css">
    <title>
        
        ArrayList HashMap源码泛读笔记｜xiuqianli&#39;s blog
        
    </title>

    <link rel="canonical" href="https://981764793.gitee.io/2018/07/18/ArrayList-HashMap源码泛读笔记/">

    <!-- Bootstrap Core CSS -->
    <link rel="stylesheet" href="/css/bootstrap.min.css">

    <!-- Custom CSS -->
    <link rel="stylesheet" href="/css/blog-style.css">

    <!-- Pygments Github CSS -->
    <link rel="stylesheet" href="/css/syntax.css">
</head>

<style>

    header.intro-header {
        background-image: url('http://oco8bvfr8.qnssl.com/blog-bg-black-run.jpg?imageView2/1/w/1400/h/400/interlace/1/q/80')
    }
</style>
<!-- hack iOS CSS :active style -->
<body ontouchstart="" class="animated fadeIn">
<!-- Navigation -->
<nav class="navbar navbar-default navbar-custom navbar-fixed-top " id="nav-top" data-ispost = "true" data-istags="false
" data-ishome = "false" >
    <div class="container-fluid">
        <!-- Brand and toggle get grouped for better mobile display -->
        <div class="navbar-header page-scroll">
            <button type="button" class="navbar-toggle">
                <span class="sr-only">Toggle navigation</span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </button>
            <a class="navbar-brand animated pulse" href="/">
                <span class="brand-logo">
                    Xiuqianli&#39;s blog
                </span>
                's Blog
            </a>
        </div>

        <!-- Collect the nav links, forms, and other content for toggling -->
        <!-- Known Issue, found by Hux:
            <nav>'s height woule be hold on by its content.
            so, when navbar scale out, the <nav> will cover tags.
            also mask any touch event of tags, unfortunately.
        -->
        <!-- /.navbar-collapse -->
        <div id="huxblog_navbar">
            <div class="navbar-collapse">
                <ul class="nav navbar-nav navbar-right">
                    <li>
                        <a href="/">Home</a>
                    </li>
					
                    
                        
							
                        <li>
                            <a href="/Tags/">Tags</a>
                        </li>
							
						
                    
					
					
                </ul>
            </div>
        </div>
    </div>
    <!-- /.container -->
</nav>
<script>
    // Drop Bootstarp low-performance Navbar
    // Use customize navbar with high-quality material design animation
    // in high-perf jank-free CSS3 implementation
//    var $body   = document.body;
    var $toggle = document.querySelector('.navbar-toggle');
    var $navbar = document.querySelector('#huxblog_navbar');
    var $collapse = document.querySelector('.navbar-collapse');

    $toggle.addEventListener('click', handleMagic)
    function handleMagic(e){
        if ($navbar.className.indexOf('in') > 0) {
        // CLOSE
            $navbar.className = " ";
            // wait until animation end.
            setTimeout(function(){
                // prevent frequently toggle
                if($navbar.className.indexOf('in') < 0) {
                    $collapse.style.height = "0px"
                }
            },400)
        }else{
        // OPEN
            $collapse.style.height = "auto"
            $navbar.className += " in";
        }
    }
</script>

<!-- Main Content -->

<!--only post-->


<img class="wechat-title-img"
     src="http://oco8bvfr8.qnssl.com/blog-bg-black-run.jpg?imageView2/1/w/1400/h/400/interlace/1/q/80">


<style>
    
    header.intro-header {
        background-image: url('http://oco8bvfr8.qnssl.com/blog-bg-black-run.jpg?imageView2/1/w/1400/h/400/interlace/1/q/80')
    }

    
</style>

<header class="intro-header">
    <div class="container">
        <div class="row">
            <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1 text-center">
                <div class="post-heading">
                    <h1>ArrayList HashMap源码泛读笔记</h1>
                    
                    <span class="meta">
                         作者 Xiuqian Li
                        <span>
                          日期 2018-07-18
                         </span>
                    </span>
                    <div class="tags text-center">
                        
                        <a class="tag" href="/tags/#java"
                           title="java">java</a>
                        
                        <a class="tag" href="/tags/#jdk源码"
                           title="jdk源码">jdk源码</a>
                        
                    </div>
                </div>
            </div>
        </div>
    </div>
    <div class="post-title-haojen">
        <span>
            ArrayList HashMap源码泛读笔记
        </span>
    </div>
</header>

<!-- Post Content -->
<article>
    <div class="container">
        <div class="row">
            <!-- Post Container -->
            <div class="col-lg-8 col-lg-offset-1 col-sm-9 post-container">
                <h3 id="ArrayList"><a href="#ArrayList" class="headerlink" title="ArrayList"></a>ArrayList</h3><p>内部用数组实现，父类有一个modCount变量记录结构变化次数。记录一下add，get,remove,clear最简单的重载方法的源码阅读记录，直接看的jdk1.8的源码可能跟其他版本有所不同。</p>
<h4 id="构造函数"><a href="#构造函数" class="headerlink" title="构造函数"></a>构造函数</h4><p>无参函数直接把elementData数组置为空数组，有一个int类型的有参构造函数传入initialCapacity， 如果大于0就把elementData设为长度为initialCapacity的数组，小于0抛出异常。另一个参数为Collection&lt;? extends E&gt; c的有参构造函数里调用collection.toArray方法得到目标集合的数组，判断长度为0就把elementData数组置为空数组， 否则调用Arrays.copyOf把数组复制到elementData。</p>
<h4 id="add-E-e"><a href="#add-E-e" class="headerlink" title="add(E e)"></a>add(E e)</h4><figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">public boolean add(E e) &#123;</span><br><span class="line">    ensureCapacityInternal(size + 1);  // Increments modCount!!</span><br><span class="line">    elementData[size++] = e;</span><br><span class="line">    return true;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>先从这个最简单的简单了解了一下ArrayList的原理。调用ensureCapacityInternal方法，一步步判断是否需要新增空间，传入参数为List当前长度加1，调用完后直接elementData[size++] = e;完成添加。</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">private void ensureCapacityInternal(int minCapacity) &#123;</span><br><span class="line">    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) &#123;</span><br><span class="line">        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    ensureExplicitCapacity(minCapacity);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">private void ensureExplicitCapacity(int minCapacity) &#123;</span><br><span class="line">    modCount++;</span><br><span class="line"></span><br><span class="line">    // overflow-conscious code</span><br><span class="line">    if (minCapacity - elementData.length &gt; 0)</span><br><span class="line">        grow(minCapacity);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">private void grow(int minCapacity) &#123;</span><br><span class="line">    // overflow-conscious code</span><br><span class="line">    int oldCapacity = elementData.length;</span><br><span class="line">    int newCapacity = oldCapacity + (oldCapacity &gt;&gt; 1);</span><br><span class="line">    if (newCapacity - minCapacity &lt; 0)</span><br><span class="line">        newCapacity = minCapacity;</span><br><span class="line">    if (newCapacity - MAX_ARRAY_SIZE &gt; 0)</span><br><span class="line">        newCapacity = hugeCapacity(minCapacity);</span><br><span class="line">    // minCapacity is usually close to size, so this is a win:</span><br><span class="line">    elementData = Arrays.copyOf(elementData, newCapacity);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">private static int hugeCapacity(int minCapacity) &#123;</span><br><span class="line">    if (minCapacity &lt; 0) // overflow</span><br><span class="line">        throw new OutOfMemoryError();</span><br><span class="line">    return (minCapacity &gt; MAX_ARRAY_SIZE) ?</span><br><span class="line">        Integer.MAX_VALUE :</span><br><span class="line">        MAX_ARRAY_SIZE;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>在ensureCapacityInternal中判断了当前数组是否为空，如果为空尝试重新计算minCapacity（minCapacity和DEFAULT_CAPACITY（10）哪个大取哪个）.</p>
<p>然后调用ensureExplicitCapacity方法，在ensureExplicitCapacity方法中根据minCapacity是否大于当前数组的长度来判断是否调用grow函数对数组进行扩容。</p>
<p>基本扩容方法是加上当前长度的1/2，也就是扩容到当前空间的1.5倍，计算时用到了位运算（：int newCapacity = oldCapacity + (oldCapacity &gt;&gt; 1);）.</p>
<p>重点有个判断调用hugeCapacity判断是否增长到Integer.MAX_VALUE或者抛出OOM异常。计算完新长度后调用Arrays.copyOf重新分配空间并把原数组复制到新数组。</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">if (newCapacity - MAX_ARRAY_SIZE &gt; 0)</span><br><span class="line">    newCapacity = hugeCapacity(minCapacity);</span><br></pre></td></tr></table></figure>
<h4 id="add-int-index-E-element"><a href="#add-int-index-E-element" class="headerlink" title="add(int index, E element)"></a>add(int index, E element)</h4><figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">public void add(int index, E element) &#123;</span><br><span class="line">    rangeCheckForAdd(index);</span><br><span class="line"></span><br><span class="line">    ensureCapacityInternal(size + 1);  // Increments modCount!!</span><br><span class="line">    System.arraycopy(elementData, index, elementData, index + 1,</span><br><span class="line">                     size - index);</span><br><span class="line">    elementData[index] = element;</span><br><span class="line">    size++;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>思路跟add(E e)基本一致，不过先调用了rangeCheckForAdd(index);检查目标index是否越界，然后调用ensureCapacityInternal(size + 1)，需要扩容的话就扩容，然后调用System.arraycopy(elementData, index,elementData, index + 1, size - index);把index开始的所有数据往后挪一位，最后elementData[index] = element;把新增数据放到目标位置</p>
<h4 id="get"><a href="#get" class="headerlink" title="get"></a>get</h4><figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">public E get(int index) &#123;</span><br><span class="line">    rangeCheck(index);</span><br><span class="line"></span><br><span class="line">    return elementData(index);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">E elementData(int index) &#123;</span><br><span class="line">    return (E) elementData[index];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>调用了rangeCheckForAdd(index);检查目标index是否越界，然后return elementData(index);直接返回数组里对应的数据。</p>
<h4 id="remove-int-index"><a href="#remove-int-index" class="headerlink" title="remove(int index)"></a>remove(int index)</h4><figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">public E remove(int index) &#123;</span><br><span class="line">    rangeCheck(index);</span><br><span class="line"></span><br><span class="line">    modCount++;</span><br><span class="line">    E oldValue = elementData(index);</span><br><span class="line"></span><br><span class="line">    int numMoved = size - index - 1;</span><br><span class="line">    if (numMoved &gt; 0)</span><br><span class="line">        System.arraycopy(elementData, index+1, elementData, index,</span><br><span class="line">                         numMoved);</span><br><span class="line">    elementData[--size] = null; // clear to let GC do its work</span><br><span class="line"></span><br><span class="line">    return oldValue;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>同样是先检查是否越界，然后E oldValue = elementData(index);取出目标位置的数据（用于方法执行完成后返回数据），然后int numMoved = size - index - 1;计算出目标位置后的数据个数（需要移动几位），然后用System.arraycopy将numMoved个数据往前挪一位，elementData[–size] = null;将长度减一以及最后一位置为null，让gc触发时可以回收数据。</p>
<h4 id="remove-Object-o"><a href="#remove-Object-o" class="headerlink" title="remove(Object o)"></a>remove(Object o)</h4><figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">public boolean remove(Object o) &#123;</span><br><span class="line">    if (o == null) &#123;</span><br><span class="line">        for (int index = 0; index &lt; size; index++)</span><br><span class="line">            if (elementData[index] == null) &#123;</span><br><span class="line">                fastRemove(index);</span><br><span class="line">                return true;</span><br><span class="line">            &#125;</span><br><span class="line">    &#125; else &#123;</span><br><span class="line">        for (int index = 0; index &lt; size; index++)</span><br><span class="line">            if (o.equals(elementData[index])) &#123;</span><br><span class="line">                fastRemove(index);</span><br><span class="line">                return true;</span><br><span class="line">            &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return false;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">private void fastRemove(int index) &#123;</span><br><span class="line">    modCount++;</span><br><span class="line">    int numMoved = size - index - 1;</span><br><span class="line">    if (numMoved &gt; 0)</span><br><span class="line">        System.arraycopy(elementData, index+1, elementData, index,</span><br><span class="line">                         numMoved);</span><br><span class="line">    elementData[--size] = null; // clear to let GC do its work</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>先判断了o是否为null，为null的话遍历数组找到第一个为null的值调用fastRemove移除，否则遍历数组，调用o.equals找到第一个相等的数据调用fastRemove移除，fastRemove原理跟remove(int index)一样，只是没有获取对应数据返回的步骤</p>
<h3 id="HashMap"><a href="#HashMap" class="headerlink" title="HashMap"></a>HashMap</h3><p>这只是个泛读，自己看到啥就尝试理解啥并记录下来，并没有进行深度了解。在java8中HashMap里用到了数组（没有hash碰撞） &gt; 链表（hash碰撞后，链表长度小于阈值） &gt; 红黑树（hash碰撞的key太多，链表长度超出阈值把链表转换成红黑树），其中链表转红黑树的阈值默认是8，也就是hash碰撞的链表长度超过8后就转为红黑树。HashMap的数据存储在一个Node&lt;K,V&gt;数组里，Node是一个实现了Map.Entry接口的内部类，</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">final int hash;</span><br><span class="line">final K key;</span><br><span class="line">V value;</span><br><span class="line">Node&lt;K,V&gt; next;</span><br></pre></td></tr></table></figure>
<p>成员变量里有hash值，KV,和next(链表结构)</p>
<p>HashMap有一个挺基础又挺重要的方法</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">static final int hash(Object key) &#123;</span><br><span class="line">    int h;</span><br><span class="line">    return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>根据key计算hashCode，key为null的话hash为0，否则调用对象的hashCode方法得到hashCode，并将hashCode无符号右移16位后与原hashCode异或运算，让低16位同时包括了高位与低位的信息，减少了hash的碰撞（因为后面要用到(n - 1) &amp; hash 计算元素在数组中的下标，按位与如果其中一个值高位全部为0的话就只有低位进行预算，所以先让hash值低位同时拥有高位和低位信息即可减少碰撞的发生）。</p>
<h4 id="构造函数-1"><a href="#构造函数-1" class="headerlink" title="构造函数"></a>构造函数</h4><p>构造函数有四个重载，分别是：</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">public HashMap(int initialCapacity, float loadFactor) &#123;</span><br><span class="line">    if (initialCapacity &lt; 0)</span><br><span class="line">        throw new IllegalArgumentException(&quot;Illegal initial capacity: &quot; +</span><br><span class="line">                                           initialCapacity);</span><br><span class="line">    if (initialCapacity &gt; MAXIMUM_CAPACITY)</span><br><span class="line">        initialCapacity = MAXIMUM_CAPACITY;</span><br><span class="line">    if (loadFactor &lt;= 0 || Float.isNaN(loadFactor))</span><br><span class="line">        throw new IllegalArgumentException(&quot;Illegal load factor: &quot; +</span><br><span class="line">                                           loadFactor);</span><br><span class="line">    this.loadFactor = loadFactor;</span><br><span class="line">    this.threshold = tableSizeFor(initialCapacity);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">public HashMap(int initialCapacity) &#123;</span><br><span class="line">    this(initialCapacity, DEFAULT_LOAD_FACTOR);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">public HashMap() &#123;</span><br><span class="line">    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">public HashMap(Map&lt;? extends K, ? extends V&gt; m) &#123;</span><br><span class="line">    this.loadFactor = DEFAULT_LOAD_FACTOR;</span><br><span class="line">    putMapEntries(m, false);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">final void putMapEntries(Map&lt;? extends K, ? extends V&gt; m, boolean evict) &#123;</span><br><span class="line">    int s = m.size();</span><br><span class="line">    if (s &gt; 0) &#123;</span><br><span class="line">        if (table == null) &#123; // pre-size</span><br><span class="line">            float ft = ((float)s / loadFactor) + 1.0F;</span><br><span class="line">            int t = ((ft &lt; (float)MAXIMUM_CAPACITY) ?</span><br><span class="line">                     (int)ft : MAXIMUM_CAPACITY);</span><br><span class="line">            if (t &gt; threshold)</span><br><span class="line">                threshold = tableSizeFor(t);</span><br><span class="line">        &#125;</span><br><span class="line">        else if (s &gt; threshold)</span><br><span class="line">            resize();</span><br><span class="line">        for (Map.Entry&lt;? extends K, ? extends V&gt; e : m.entrySet()) &#123;</span><br><span class="line">            K key = e.getKey();</span><br><span class="line">            V value = e.getValue();</span><br><span class="line">            putVal(hash(key), key, value, false, evict);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>第一个用于设置初始大小和扩容因子（扩容因子默认为0.75），第二个只设置扩容因子，第三个使用默认的扩容因子0.75，第四个用于将旧的Map构造成新的HashMap，调用了putMapEntries，在里面根据旧Map的大小，判断是否重新分配空间，然后遍历旧Map的entrySet调用putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)添加到新Map中。</p>
<p>其中调用到tableSizeFor(int cap)计算空间扩容阈值，一串位运算，暂时不太理解。</p>
<h4 id="resize"><a href="#resize" class="headerlink" title="resize"></a>resize</h4><p>重新分配容量（数组大小），用于分配初始空间和新增元素后数组长度达到扩容阈值后（即已使用数组空间的0.75（默认扩容因子）后）进行扩容</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">final Node&lt;K,V&gt;[] resize() &#123;</span><br><span class="line">        Node&lt;K,V&gt;[] oldTab = table;</span><br><span class="line">        int oldCap = (oldTab == null) ? 0 : oldTab.length;</span><br><span class="line">        int oldThr = threshold;</span><br><span class="line">        int newCap, newThr = 0;</span><br><span class="line">        if (oldCap &gt; 0) &#123;</span><br><span class="line">            if (oldCap &gt;= MAXIMUM_CAPACITY) &#123;</span><br><span class="line">                threshold = Integer.MAX_VALUE;</span><br><span class="line">                return oldTab;</span><br><span class="line">            &#125;</span><br><span class="line">            else if ((newCap = oldCap &lt;&lt; 1) &lt; MAXIMUM_CAPACITY &amp;&amp;</span><br><span class="line">                     oldCap &gt;= DEFAULT_INITIAL_CAPACITY)</span><br><span class="line">                newThr = oldThr &lt;&lt; 1; // double threshold</span><br><span class="line">        &#125;</span><br><span class="line">        else if (oldThr &gt; 0) // initial capacity was placed in threshold</span><br><span class="line">            newCap = oldThr;</span><br><span class="line">        else &#123;               // zero initial threshold signifies using defaults</span><br><span class="line">            newCap = DEFAULT_INITIAL_CAPACITY;</span><br><span class="line">            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);</span><br><span class="line">        &#125;</span><br><span class="line">        if (newThr == 0) &#123;</span><br><span class="line">            float ft = (float)newCap * loadFactor;</span><br><span class="line">            newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (float)MAXIMUM_CAPACITY ?</span><br><span class="line">                      (int)ft : Integer.MAX_VALUE);</span><br><span class="line">        &#125;</span><br><span class="line">        threshold = newThr;</span><br><span class="line">        @SuppressWarnings(&#123;&quot;rawtypes&quot;,&quot;unchecked&quot;&#125;)</span><br><span class="line">            Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])new Node[newCap];</span><br><span class="line">        table = newTab;</span><br><span class="line">        if (oldTab != null) &#123;</span><br><span class="line">            for (int j = 0; j &lt; oldCap; ++j) &#123;</span><br><span class="line">                Node&lt;K,V&gt; e;</span><br><span class="line">                if ((e = oldTab[j]) != null) &#123;</span><br><span class="line">                    oldTab[j] = null;</span><br><span class="line">                    if (e.next == null)</span><br><span class="line">                        newTab[e.hash &amp; (newCap - 1)] = e;</span><br><span class="line">                    else if (e instanceof TreeNode)</span><br><span class="line">                        ((TreeNode&lt;K,V&gt;)e).split(this, newTab, j, oldCap);</span><br><span class="line">                    else &#123; // preserve order</span><br><span class="line">                        Node&lt;K,V&gt; loHead = null, loTail = null;</span><br><span class="line">                        Node&lt;K,V&gt; hiHead = null, hiTail = null;</span><br><span class="line">                        Node&lt;K,V&gt; next;</span><br><span class="line">                        do &#123;</span><br><span class="line">                            next = e.next;</span><br><span class="line">                            if ((e.hash &amp; oldCap) == 0) &#123;</span><br><span class="line">                                if (loTail == null)</span><br><span class="line">                                    loHead = e;</span><br><span class="line">                                else</span><br><span class="line">                                    loTail.next = e;</span><br><span class="line">                                loTail = e;</span><br><span class="line">                            &#125;</span><br><span class="line">                            else &#123;</span><br><span class="line">                                if (hiTail == null)</span><br><span class="line">                                    hiHead = e;</span><br><span class="line">                                else</span><br><span class="line">                                    hiTail.next = e;</span><br><span class="line">                                hiTail = e;</span><br><span class="line">                            &#125;</span><br><span class="line">                        &#125; while ((e = next) != null);</span><br><span class="line">                        if (loTail != null) &#123;</span><br><span class="line">                            loTail.next = null;</span><br><span class="line">                            newTab[j] = loHead;</span><br><span class="line">                        &#125;</span><br><span class="line">                        if (hiTail != null) &#123;</span><br><span class="line">                            hiTail.next = null;</span><br><span class="line">                            newTab[j + oldCap] = hiHead;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        return newTab;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<p>如果当前长度以及大于MAXIMUM_CAPACITY（1 &lt;&lt; 30： 1073741824）就把扩容阈值设为Integer.MAX_VALUE，不进行扩容直接return</p>
<p>否则就开始尝试将当前长度乘2作为新容量，并判断是否满足大于等于DEFAULT_INITIAL_CAPACITY（16）并且小于MAXIMUM_CAPACITY这个条件，满足就将扩容阈值乘2作为新的扩容阈值。</p>
<p>如果当前长度为0但是扩容阈值大于0，就将扩容阈值作为新容量</p>
<p>以上条件都不满足的话根据默认值进行初始化，及新容量为DEFAULT_INITIAL_CAPACITY，新扩容阈值为DEFAULT_INITIAL_CAPACITY乘扩容因子DEFAULT_LOAD_FACTOR（默认0.75）。</p>
<p>如果一串操作之后新扩容阈值还是为0就执行下面这串代码，尝试着用新容量乘扩容因子作为新扩容阈值</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">if (newThr == 0) &#123;</span><br><span class="line">    float ft = (float)newCap * loadFactor;</span><br><span class="line">    newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (float)MAXIMUM_CAPACITY ?</span><br><span class="line">        (int)ft : Integer.MAX_VALUE);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>后面就是分配一个新的Node数组，并把旧数组里的所有元素复制到新数组里,最后把之前的数据复制到新数组里。</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])new Node[newCap];</span><br></pre></td></tr></table></figure>
<h4 id="put"><a href="#put" class="headerlink" title="put"></a>put</h4><p>直接调用的putVal：</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">final V putVal(int hash, K key, V value, boolean onlyIfAbsent,</span><br><span class="line">                   boolean evict) &#123;</span><br><span class="line">        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; int n, i;</span><br><span class="line">        if ((tab = table) == null || (n = tab.length) == 0)</span><br><span class="line">            n = (tab = resize()).length;</span><br><span class="line">        if ((p = tab[i = (n - 1) &amp; hash]) == null)</span><br><span class="line">            tab[i] = newNode(hash, key, value, null);</span><br><span class="line">        else &#123;</span><br><span class="line">            Node&lt;K,V&gt; e; K k;</span><br><span class="line">            if (p.hash == hash &amp;&amp;</span><br><span class="line">                ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))</span><br><span class="line">                e = p;</span><br><span class="line">            else if (p instanceof TreeNode)</span><br><span class="line">                e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(this, tab, hash, key, value);</span><br><span class="line">            else &#123;</span><br><span class="line">                for (int binCount = 0; ; ++binCount) &#123;</span><br><span class="line">                    if ((e = p.next) == null) &#123;</span><br><span class="line">                        p.next = newNode(hash, key, value, null);</span><br><span class="line">                        if (binCount &gt;= TREEIFY_THRESHOLD - 1) // -1 for 1st</span><br><span class="line">                            treeifyBin(tab, hash);</span><br><span class="line">                        break;</span><br><span class="line">                    &#125;</span><br><span class="line">                    if (e.hash == hash &amp;&amp;</span><br><span class="line">                        ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))</span><br><span class="line">                        break;</span><br><span class="line">                    p = e;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            if (e != null) &#123; // existing mapping for key</span><br><span class="line">                V oldValue = e.value;</span><br><span class="line">                if (!onlyIfAbsent || oldValue == null)</span><br><span class="line">                    e.value = value;</span><br><span class="line">                afterNodeAccess(e);</span><br><span class="line">                return oldValue;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        ++modCount;</span><br><span class="line">        if (++size &gt; threshold)</span><br><span class="line">            resize();</span><br><span class="line">        afterNodeInsertion(evict);</span><br><span class="line">        return null;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<p>前三参数个字面意思理解，onlyIfAbsent是判断是否只在原有的值为null的时候覆盖。执行过程是先判断当前table (Node数组)是否分配了空间，没有就分配一下，然后判断hash是否存在于当前Node数组中</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">if ((p = tab[i = (n - 1) &amp; hash]) == null)</span><br><span class="line">    tab[i] = newNode(hash, key, value, null);</span><br></pre></td></tr></table></figure>
<p>原理就是用(n - 1) &amp; hash计算出下标，其中n为当前Node数组的长度，这个按位与其实就是相当于hash % n，如果当前下标的元素为null就代表当前数组里还没有这个hash，直接新建一个Node放在这个位置，newNode方法就是new了一个Node（猜测这个方法是为了方便以后版本对这步操作加强而预留的）。</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">Node&lt;K,V&gt; newNode(int hash, K key, V value, Node&lt;K,V&gt; next) &#123;</span><br><span class="line">    return new Node&lt;&gt;(hash, key, value, next);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>如果这个根据hash计算出来的位置有值了，就判断key到底是不是相同的，相同就直接覆盖掉之前的value（在这里只是保存了旧的节点（Node），还没有进行value的覆盖）</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">if (p.hash == hash &amp;&amp;</span><br><span class="line">    ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))</span><br><span class="line">        e = p;</span><br></pre></td></tr></table></figure>
<p>这里同时根据hash、key引用地址、key.equals进行判断key是否相同</p>
<p>如果不符合这个条件就代表只是两个key的hash碰撞了，实际上并不是同一个key，所以接着往下判断当前的Node是不是TreeNode（java8的hashmap中用到了红黑树, TreeNode继承于LinkedHashMap.Entry），是的话就直接把值put进红黑树里，因为数据结构这部分有点渣，TreeNode的实现不太看得懂，所以暂时没往下看</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">else if (p instanceof TreeNode)</span><br><span class="line">    e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(this, tab, hash, key, value);</span><br></pre></td></tr></table></figure>
<p>接下来就是hash碰撞后存到链表的解决方案了</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">else &#123;</span><br><span class="line">    for (int binCount = 0; ; ++binCount) &#123;</span><br><span class="line">        if ((e = p.next) == null) &#123;</span><br><span class="line">            p.next = newNode(hash, key, value, null);</span><br><span class="line">            if (binCount &gt;= TREEIFY_THRESHOLD - 1) // -1 for 1st</span><br><span class="line">                treeifyBin(tab, hash);</span><br><span class="line">            break;</span><br><span class="line">        &#125;</span><br><span class="line">        if (e.hash == hash &amp;&amp;</span><br><span class="line">            ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))</span><br><span class="line">            break;</span><br><span class="line">            p = e;</span><br><span class="line">        &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>遍历链表（Node就是个链表），如果发现了key相同的节点就跳出循环，否则直接遍历到链表的尾部，链表到头了就直接在尾部接上一个新节点，接完之后判断一下链表长度是否达到需要转换为红黑树的阈值，达到了就把这个链表转为红黑树。</p>
<p>接下来就到了找到key相同Node后进行值覆盖的代码</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">if (e != null) &#123; // existing mapping for key</span><br><span class="line">    V oldValue = e.value;</span><br><span class="line">    if (!onlyIfAbsent || oldValue == null)</span><br><span class="line">        e.value = value;</span><br><span class="line">        afterNodeAccess(e);</span><br><span class="line">        return oldValue;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<p>e 不等于null就代表key已存在，先取出旧的值，然后判断一下是否只在旧值为null的时候覆盖，满足条件就覆盖并返回旧的值，其中调用了一个空方法afterNodeAccess,据说以下三个空方法都是为了方便实现LinkedHashMap而预留的回调，暂时没看LinkedHashMap没法确认。</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">void afterNodeAccess(Node&lt;K,V&gt; p) &#123; &#125;</span><br><span class="line">void afterNodeInsertion(boolean evict) &#123; &#125;</span><br><span class="line">void afterNodeRemoval(Node&lt;K,V&gt; p) &#123; &#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">++modCount;</span><br><span class="line">if (++size &gt; threshold)</span><br><span class="line">    resize();</span><br><span class="line">afterNodeInsertion(evict);</span><br><span class="line">return null;</span><br></pre></td></tr></table></figure>
<p>在最后如果是新增key的话就对modCount自增（ArrayList说过这个变量是记录结构修改次数的，新增元素当然算是修改一次了），然后判断是否需要扩容。</p>
<h4 id="get-Object-key"><a href="#get-Object-key" class="headerlink" title="get(Object key)"></a>get(Object key)</h4><figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">public V get(Object key) &#123;</span><br><span class="line">        Node&lt;K,V&gt; e;</span><br><span class="line">        return (e = getNode(hash(key), key)) == null ? null : e.value;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<p>调用getNode方法，根据key的hashCode和key本身查找对应的节点，节点不为null就返回节点的值，否则直接返回null</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">final Node&lt;K,V&gt; getNode(int hash, Object key) &#123;</span><br><span class="line">        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; int n; K k;</span><br><span class="line">        if ((tab = table) != null &amp;&amp; (n = tab.length) &gt; 0 &amp;&amp;</span><br><span class="line">            (first = tab[(n - 1) &amp; hash]) != null) &#123;</span><br><span class="line">            if (first.hash == hash &amp;&amp; // always check first node</span><br><span class="line">                ((k = first.key) == key || (key != null &amp;&amp; key.equals(k))))</span><br><span class="line">                return first;</span><br><span class="line">            if ((e = first.next) != null) &#123;</span><br><span class="line">                if (first instanceof TreeNode)</span><br><span class="line">                    return ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);</span><br><span class="line">                do &#123;</span><br><span class="line">                    if (e.hash == hash &amp;&amp;</span><br><span class="line">                        ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))</span><br><span class="line">                        return e;</span><br><span class="line">                &#125; while ((e = e.next) != null);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        return null;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<p>首先判断Node数组是否为空，然后尝试根据hash计算下标取对应的节点，如果数组为空或者对应下标不存在就返回null。</p>
<p>拿到对应下标的节点尝试判断key是不是真的相符，相符就代表已经找到了对的Node，直接返回，没有的话就代表这个hash发生过碰撞，进行下一步判断，判断链表是否已经转换成红黑树，已经转换了就调用红黑树的查询，否则就遍历链表查找对应Node，如果找不到就代表map里没有这个key。所以hashmap的查找的速度很快，没碰撞的情况下时间复杂度O（1），只是简单的根据hash计算数组下标，如果发生了hash碰撞的话遍历链表时间复杂度O（n），但是最多遍历8次而已，也是极快的。如果碰撞再厉害一些，超过了8次就从红黑树里查找，百度了一下时间复杂度应该是O(logn)。</p>
<h4 id="remove-Object-key"><a href="#remove-Object-key" class="headerlink" title="remove(Object key)"></a>remove(Object key)</h4><figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">public V remove(Object key) &#123;</span><br><span class="line">        Node&lt;K,V&gt; e;</span><br><span class="line">        return (e = removeNode(hash(key), key, null, false, true)) == null ?</span><br><span class="line">            null : e.value;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<p>这个方法是尝试移除元素并且返回被移除的值。重点在removeNode里</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">final Node&lt;K,V&gt; removeNode(int hash, Object key, Object value,</span><br><span class="line">                               boolean matchValue, boolean movable) &#123;</span><br><span class="line">        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; int n, index;</span><br><span class="line">        if ((tab = table) != null &amp;&amp; (n = tab.length) &gt; 0 &amp;&amp;</span><br><span class="line">            (p = tab[index = (n - 1) &amp; hash]) != null) &#123;</span><br><span class="line">            Node&lt;K,V&gt; node = null, e; K k; V v;</span><br><span class="line">            if (p.hash == hash &amp;&amp;</span><br><span class="line">                ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))</span><br><span class="line">                node = p;</span><br><span class="line">            else if ((e = p.next) != null) &#123;</span><br><span class="line">                if (p instanceof TreeNode)</span><br><span class="line">                    node = ((TreeNode&lt;K,V&gt;)p).getTreeNode(hash, key);</span><br><span class="line">                else &#123;</span><br><span class="line">                    do &#123;</span><br><span class="line">                        if (e.hash == hash &amp;&amp;</span><br><span class="line">                            ((k = e.key) == key ||</span><br><span class="line">                             (key != null &amp;&amp; key.equals(k)))) &#123;</span><br><span class="line">                            node = e;</span><br><span class="line">                            break;</span><br><span class="line">                        &#125;</span><br><span class="line">                        p = e;</span><br><span class="line">                    &#125; while ((e = e.next) != null);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            if (node != null &amp;&amp; (!matchValue || (v = node.value) == value ||</span><br><span class="line">                                 (value != null &amp;&amp; value.equals(v)))) &#123;</span><br><span class="line">                if (node instanceof TreeNode)</span><br><span class="line">                    ((TreeNode&lt;K,V&gt;)node).removeTreeNode(this, tab, movable);</span><br><span class="line">                else if (node == p)</span><br><span class="line">                    tab[index] = node.next;</span><br><span class="line">                else</span><br><span class="line">                    p.next = node.next;</span><br><span class="line">                ++modCount;</span><br><span class="line">                --size;</span><br><span class="line">                afterNodeRemoval(node);</span><br><span class="line">                return node;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        return null;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<p>前边的代码跟getNode一样，就是先找到目标节点。真正进行移除的代码是下面这一段：</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">if (node != null &amp;&amp; (!matchValue || (v = node.value) == value ||</span><br><span class="line">    (value != null &amp;&amp; value.equals(v)))) &#123;</span><br><span class="line">    if (node instanceof TreeNode)</span><br><span class="line">        ((TreeNode&lt;K,V&gt;)node).removeTreeNode(this, tab, movable);</span><br><span class="line">    else if (node == p)</span><br><span class="line">        tab[index] = node.next;</span><br><span class="line">    else</span><br><span class="line">        p.next = node.next;</span><br><span class="line">    ++modCount;</span><br><span class="line">    --size;</span><br><span class="line">    afterNodeRemoval(node);</span><br><span class="line">    return node;</span><br></pre></td></tr></table></figure>
<p>}<br>先判断node不为null，根据matchValue参数判断是否判断值匹配，remove(Object key）里调用时是false,remove还有另一个重载remove(Object key, Object value)，这个是当value也相同的时候才移除。</p>
<p>移除的逻辑是先判断Node是否是TreeNode（链表是否已转换成红黑树），是的话调用红黑树的移除，否则判断是否是头结点（没有发生hash碰撞或者发生了碰撞但是是头结点），直接把node.next覆盖到数组里，如果之前两个都不满足的话就代表要移除的节点在链表里，直接p.next = node.next;</p>
<h3 id="结语"><a href="#结语" class="headerlink" title="结语"></a>结语</h3><p>以上就是我这两天看的部分源码，虽然没深入了解到哪去，但是对ArrayList和HaspMap常用方法的基本的原理和实现流程有了一定的理解，有所不足的就是对红黑树实现还是看不太懂，然后简单看了一下jdk7的hashmap实现，jdk7里没有Node只有Entry，实际上都一样，都是链表结构，但是jdk7发生hash碰撞后直接加进链表里没有红黑树的实现。过段有空可以尝试着写两个小轮子自己试试只有简单增删改查的MyArrayList和MyHaspMap加强一下记忆。</p>

                <hr>
                

                <ul class="pager">
                    
                    <li class="previous">
                        <a href="/2018/07/18/ThreadLocal源码泛读笔记/" data-toggle="tooltip" data-placement="top"
                           title="ThreadLocal源码泛读笔记">&larr; Previous Post</a>
                    </li>
                    
                    
                    <li class="next">
                        <a href="/2018/07/17/手写山寨spring基础功能-MVC-2-异常处理和视图处理/" data-toggle="tooltip" data-placement="top"
                           title="手写山寨spring基础功能 - MVC(2) - 异常处理和视图处理">Next Post &rarr;</a>
                    </li>
                    
                </ul>

                

                


                <!--加入新的评论系统-->
                
            </div>

            <div class="hidden-xs col-sm-3 toc-col">
                <div class="toc-wrap">
                    <ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#ArrayList"><span class="toc-text">ArrayList</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#构造函数"><span class="toc-text">构造函数</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#add-E-e"><span class="toc-text">add(E e)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#add-int-index-E-element"><span class="toc-text">add(int index, E element)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#get"><span class="toc-text">get</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#remove-int-index"><span class="toc-text">remove(int index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#remove-Object-o"><span class="toc-text">remove(Object o)</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap"><span class="toc-text">HashMap</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#构造函数-1"><span class="toc-text">构造函数</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#resize"><span class="toc-text">resize</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#put"><span class="toc-text">put</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#get-Object-key"><span class="toc-text">get(Object key)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#remove-Object-key"><span class="toc-text">remove(Object key)</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#结语"><span class="toc-text">结语</span></a></li></ol>
                </div>
            </div>
        </div>

        <div class="row">
            <!-- Sidebar Container -->

            <div class="
                col-lg-8 col-lg-offset-2
                col-md-10 col-md-offset-1
                sidebar-container">

                <!-- Featured Tags -->
                
                <section>
                    <!-- no hr -->
                    <h5 class="text-center">
                        <a href="/tags/">FEATURED TAGS</a>
                    </h5>
                    <div class="tags">
                        
                        <a class="tag" href="/tags/#java"
                           title="java">java</a>
                        
                        <a class="tag" href="/tags/#jdk源码"
                           title="jdk源码">jdk源码</a>
                        
                    </div>
                </section>
                

                <!-- Friends Blog -->
                
            </div>
        </div>

    </div>
</article>







<!-- Footer -->
<!-- Footer -->
<footer>
    <div class="container">
        <div class="row">
            <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1 text-center">
                <br>
                <ul class="list-inline text-center">
                
                
                
                    <li>
                        <a target="_blank" href="https://www.zhihu.com/people/asdf1234-97">
                            <span class="fa-stack fa-lg">
                                <i class="fa fa-circle fa-stack-2x"></i>
                                <i class="fa  fa-stack-1x fa-inverse">知</i>
                            </span>
                        </a>
                    </li>
                

                

                

                
                    <li>
                        <a target="_blank"  href="https://github.com/xiuqianli1996">
                            <span class="fa-stack fa-lg">
                                <i class="fa fa-circle fa-stack-2x"></i>
                                <i class="fa fa-github fa-stack-1x fa-inverse"></i>
                            </span>
                        </a>
                    </li>
                

                

                </ul>
                <p class="copyright text-muted">
                    Copyright &copy; Xiuqianli&#39;s blog 2018
                    <br>
                    <span id="busuanzi_container_site_pv" style="font-size: 12px;">PV: <span id="busuanzi_value_site_pv"></span> Times</span>
                    <br>
                    Theme by <a href="https://haojen.github.io/">Haojen Ma</a>
                </p>

            </div>
        </div>
    </div>
</footer>

<!-- jQuery -->
<script src="/js/jquery.min.js"></script>

<!-- Bootstrap Core JavaScript -->
<script src="/js/bootstrap.min.js"></script>

<!-- Custom Theme JavaScript -->
<script src="/js/blog.js"></script>

<!-- async load function -->
<script>
    function async(u, c) {
      var d = document, t = 'script',
          o = d.createElement(t),
          s = d.getElementsByTagName(t)[0];
      o.src = u;
      if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
      s.parentNode.insertBefore(o, s);
    }
</script>

<!-- jquery.tagcloud.js -->
<script>
    // only load tagcloud.js in tag.html
    if($('#tag_cloud').length !== 0){
        async("https://981764793.gitee.io/js/jquery.tagcloud.js",function(){
            $.fn.tagcloud.defaults = {
                //size: {start: 1, end: 1, unit: 'em'},
                color: {start: '#bbbbee', end: '#0085a1'},
            };
            $('#tag_cloud a').tagcloud();
        })
    }
</script>

<!--fastClick.js -->
<script>
    async("//cdn.bootcss.com/fastclick/1.0.6/fastclick.min.js", function(){
        var $nav = document.querySelector("nav");
        if($nav) FastClick.attach($nav);
    })
</script>

<!-- Google Analytics -->



<!-- Baidu Tongji -->


<!-- swiftype -->
<script type="text/javascript">
  (function(w,d,t,u,n,s,e){w['SwiftypeObject']=n;w[n]=w[n]||function(){
  (w[n].q=w[n].q||[]).push(arguments);};s=d.createElement(t);
  e=d.getElementsByTagName(t)[0];s.async=1;s.src=u;e.parentNode.insertBefore(s,e);
  })(window,document,'script','//s.swiftypecdn.com/install/v2/st.js','_st');

  _st('install','null','2.0.0');
</script>

<script async src="//dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>

<!--wechat title img-->
<img class="wechat-title-img" src="null">
</body>

</html>
